{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Boolean Evaluation LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countEval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #布尔运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 <code>0</code> (false)、<code>1</code> (true)、<code>&amp;</code> (AND)、 <code>|</code> (OR) 和 <code>^</code> (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>s = &quot;1^0|0|1&quot;, result = 0\n",
    "\n",
    "<strong>输出: </strong>2\n",
    "<strong>解释:</strong>&nbsp;两种可能的括号方法是\n",
    "1^(0|(0|1))\n",
    "1^((0|0)|1)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>s = &quot;0&amp;0&amp;0&amp;1^1|0&quot;, result = 1\n",
    "\n",
    "<strong>输出: </strong>10</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>运算符的数量不超过 19 个</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [boolean-evaluation-lcci](https://leetcode.cn/problems/boolean-evaluation-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [boolean-evaluation-lcci](https://leetcode.cn/problems/boolean-evaluation-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        \"\"\"\n",
    "        {\n",
    "            符号: {\n",
    "                需要计算出的结果: {\n",
    "                    [(左子式需要计算的结果，右子式需要计算的结果)]\n",
    "                }\n",
    "            }\n",
    "            \n",
    "        }\n",
    "        \"\"\"\n",
    "        self.ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s, result, {})\n",
    "        \n",
    "    def dfs(self,expression,result,memo):\n",
    "        if (expression,result) in memo:\n",
    "            return memo[(expression,result)]\n",
    "        if len(expression)==1:\n",
    "            val=int(expression)\n",
    "            return int(bool(val)==result)\n",
    "        total=0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr,rr in self.ops[expression[i]][result]:\n",
    "                    total+=self.dfs(expression[:i],lr,memo)*self.dfs(expression[i+1:],rr,memo)\n",
    "                    memo[(expression,result)]=total\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s, result, {})\n",
    "\n",
    "    def dfs(self, expression, result, memo):\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "\n",
    "        if len(expression) == 1:\n",
    "            return int(bool(int(expression)) == result)\n",
    "\n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr, rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[:i], lr, memo) * self.dfs(expression[i + 1:], rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Dict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.ops = {\n",
    "            \"&\": {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)],\n",
    "            },\n",
    "            \"|\": {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)],\n",
    "            },\n",
    "            \"^\": {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)],\n",
    "            },\n",
    "        }\n",
    "        return self.__dfs(s, result, {})\n",
    "\n",
    "    def __dfs(self, expression: str, result: int, memo: Dict) -> int:\n",
    "        # 查询备忘录，有结果则直接返回\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "\n",
    "        # 边界情况\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(val == result)\n",
    "\n",
    "        # 递归计算左右子式的结果\n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            char = expression[i]\n",
    "            if char in self.ops:\n",
    "                for lr, rr in self.ops[char][bool(result)]:\n",
    "                    left = expression[:i]\n",
    "                    right = expression[i + 1 :]\n",
    "                    total += self.__dfs(left, lr, memo) * self.__dfs(right, rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.ops = {\n",
    "            '&': {\n",
    "                True:[(True, True)],\n",
    "                False:[(True, False),(False, True),(False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True:[(True, False),(False, True),(True, True)],\n",
    "                False:[(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                False:[(True, True),(False, False)],\n",
    "                True:[(True, False),(False, True)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s, result, {})\n",
    "    def dfs(self, expression, result, memo):\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(bool(val) == result)\n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr, rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[:i], lr, memo) * self.dfs(expression[i + 1 :], rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        N = len(s)\n",
    "        TMap = [[0] * N for _ in range(N)]\n",
    "        FMap = [[0] * N for _ in range(N)]\n",
    "        for i in range(0, N, 2):\n",
    "            TMap[i][i] = 1 if s[i] == '1' else 0\n",
    "            FMap[i][i] = 0 if s[i] == '1' else 1\n",
    "\n",
    "        for row in range(N - 3, -1, -2):\n",
    "            for col in range(row + 2, N, 2):\n",
    "                for k in range(row + 1, col, 2):\n",
    "                    if s[k] == '&':\n",
    "                        TMap[row][col] += TMap[row][k - 1] * TMap[k + 1][col]\n",
    "                        FMap[row][col] += (TMap[row][k - 1] * FMap[k + 1][col] +\n",
    "                                        FMap[row][k - 1] * TMap[k + 1][col] +\n",
    "                                        FMap[row][k - 1] * FMap[k + 1][col])\n",
    "                    elif s[k] == '|':\n",
    "                        TMap[row][col] += (TMap[row][k - 1] * FMap[k + 1][col] +\n",
    "                                        FMap[row][k - 1] * TMap[k + 1][col] +\n",
    "                                        TMap[row][k - 1] * TMap[k + 1][col])\n",
    "                        FMap[row][col] += FMap[row][k - 1] * FMap[k + 1][col]\n",
    "                    elif s[k] == '^':\n",
    "                        TMap[row][col] += (FMap[row][k - 1] * TMap[k + 1][col] +\n",
    "                                        TMap[row][k - 1] * FMap[k + 1][col])\n",
    "                        FMap[row][col] += (TMap[row][k - 1] * TMap[k + 1][col] +\n",
    "                                        FMap[row][k - 1] * FMap[k + 1][col])\n",
    "\n",
    "        return TMap[0][N - 1] if result else FMap[0][N - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "#         logic_dict = {\"1&1\": \"1\", \"1|1\": \"1\", \"1^1\": \"0\",\n",
    "#                      \"0&1\": \"0\", \"0|1\": \"1\", \"0^1\": \"1\",\n",
    "#                      \"1&0\": \"0\", \"1|0\": \"1\", \"1^0\": \"1\",\n",
    "#                      \"0&0\": \"0\", \"0|0\": \"0\", \"0^0\": \"0\"}\n",
    "#         if len(s) == 1:\n",
    "#             return 1 if int(s) == result else 0\n",
    "        \n",
    "#         self.count = {}\n",
    "#         def help(s0, path):\n",
    "#             if s0 in logic_dict:\n",
    "#                 if int(logic_dict[s0]) == result:\n",
    "#                     path = \"\".join(path)\n",
    "#                     if path not in self.count:\n",
    "#                         self.count[path] = 0\n",
    "#                     self.count[path] += 1\n",
    "#                 return\n",
    "            \n",
    "#             for i in range(1, len(s0), 2):\n",
    "#                 new_s0 = s0[:i-1] + logic_dict[s0[i-1:i+2]] + s0[i+2:]\n",
    "#                 new_path = path[:i-1] + [\"(\" + \"\".join(path[i-1:i+2]) + \")\"] + path[i+2:]\n",
    "#                 help(new_s0, new_path)\n",
    "        \n",
    "#         help(s, list(s))\n",
    "#         return len(self.count.keys())\n",
    "        nop = len(s) // 2\n",
    "        nval = nop + 1\n",
    "        dp = [[[0 for i in range(nval)] for j in range(nval)] for v in (0, 1)]\n",
    "        for i in range(nval):\n",
    "            dp[int(s[2 * i])][i][i] = 1\n",
    "        for r in range(1, nval):          ## increasing intv length\n",
    "            for i in range(nval - r):     ## enumerating intv start\n",
    "                j = i + r\n",
    "                for k in range(i, j):\n",
    "                    op = s[2 * k + 1]\n",
    "                    if op == '&':    ## and logic\n",
    "                        dp[1][i][j] += dp[1][i][k] * dp[1][k+1][j]\n",
    "                        dp[0][i][j] += ((dp[0][i][k] + dp[1][i][k]) * (dp[0][k+1][j] + dp[1][k+1][j]) - dp[1][i][k] * dp[1][k+1][j])\n",
    "                    elif op == '|':  ## or logic\n",
    "                        dp[0][i][j] += dp[0][i][k] * dp[0][k+1][j]\n",
    "                        dp[1][i][j] += ((dp[0][i][k] + dp[1][i][k]) * (dp[0][k+1][j] + dp[1][k+1][j]) - dp[0][i][k] * dp[0][k+1][j])\n",
    "                    else:            ## xor logic\n",
    "                        dp[0][i][j] += dp[0][i][k] * dp[0][k+1][j] + dp[1][i][k] * dp[1][k+1][j]\n",
    "                        dp[1][i][j] += dp[1][i][k] * dp[0][k+1][j] + dp[0][i][k] * dp[1][k+1][j]\n",
    "        return dp[result][0][nval - 1]\n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def countEval(self, s: str, result: int) -> int:\n",
    "    l = len(s)\n",
    "    dp = [[[0, 0] for _ in range(l)] for _ in range(l)]\n",
    "    for i in range(l):\n",
    "      if \"1\" == s[i]:\n",
    "        dp[i][i][1] = 1\n",
    "      elif \"0\" == s[i]:\n",
    "        dp[i][i][0] = 1\n",
    "\n",
    "    for i in range(3, l + 2, 2):\n",
    "      for j in range(0, l - i + 1):\n",
    "        k = j + i - 1\n",
    "        for m in range(j, k + 1):\n",
    "          am, bm = m - 1, m + 1\n",
    "          # print(f\"{m} => {j} ~ {k}\")\n",
    "          c = s[m]\n",
    "          if '&' == c:\n",
    "            dp[j][k][0] = dp[j][k][0] + dp[j][am][0] * dp[bm][k][0] + dp[j][am][1] * dp[bm][k][0] + dp[j][am][0] * dp[bm][k][1]\n",
    "            dp[j][k][1] = dp[j][k][1] + dp[j][am][1] * dp[bm][k][1]\n",
    "          elif '|' == c:\n",
    "            dp[j][k][0] = dp[j][k][0] + dp[j][am][0] * dp[bm][k][0]\n",
    "            dp[j][k][1] = dp[j][k][1] + dp[j][am][0] * dp[bm][k][1] + dp[j][am][1] * dp[bm][k][0] + dp[j][am][1] * dp[bm][k][1]\n",
    "            # print(f\" | find {dp[j][k]} {j}=>{k} m {m} i {i}\")\n",
    "          elif '^' == c:\n",
    "            dp[j][k][0] = dp[j][k][0] + dp[j][am][0] * dp[bm][k][0] + dp[j][am][1] * dp[bm][k][1]\n",
    "            dp[j][k][1] = dp[j][k][1] + dp[j][am][0] * dp[bm][k][1] + dp[j][am][1] * dp[bm][k][0]\n",
    "        # print(f\"eval {j} ~ {k} {dp[j][k]}\")\n",
    "    # dump(dp)\n",
    "    return dp[0][l - 1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.ops = {\n",
    "            \"&\":{\n",
    "                True:[(True,True)],\n",
    "                False:[(False,False),(True,False),(False,True)]\n",
    "            },\n",
    "            \"|\":{\n",
    "                True:[(True,True),(True,False),(False,True)],\n",
    "                False:[(False,False)]\n",
    "            },\n",
    "            \"^\":{\n",
    "                True:[(True,False),(False,True)],\n",
    "                False:[(False,False),(True,True)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s,result,{})\n",
    "\n",
    "    def dfs(self,expression,result,memo):\n",
    "        if (expression,result) in memo:\n",
    "            return memo[(expression,result)]\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(bool(val) == result)\n",
    "\n",
    "        total = 0 \n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr,rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[:i],lr,memo) * self.dfs(expression[i+1:],rr,memo)\n",
    "        memo[(expression,result)] = total \n",
    "        return total\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        def f1(s,l,r,dp):\n",
    "            if dp[l][r] != None:\n",
    "                return dp[l][r]\n",
    "            f = 0\n",
    "            t = 0\n",
    "            if l==r:\n",
    "                f = 1 if s[l]==\"0\" else 0\n",
    "                t = 1 if s[l]==\"1\" else 0\n",
    "            else:\n",
    "                for k in range(l+1,r,2):\n",
    "                    tmp = f1(s,l,k-1,dp)\n",
    "                    a = tmp[0]\n",
    "                    b = tmp[1]\n",
    "                    tmp = f1(s,k+1,r,dp)\n",
    "                    c = tmp[0]\n",
    "                    d = tmp[1]\n",
    "                    if s[k]==\"&\":\n",
    "                        f += a*c+a*d+b*c\n",
    "                        t += b*d\n",
    "                    elif s[k]==\"|\":\n",
    "                        f += a*c\n",
    "                        t += a*d+b*c+b*d\n",
    "                    else:\n",
    "                        f += a*c+b*d\n",
    "                        t += a*d+b*c\n",
    "            ft = [f,t]\n",
    "            dp[l][r] = ft\n",
    "            return ft\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [[None for _ in range(n)] for _ in range(n)]\n",
    "        ft = f1(s,0,n-1,dp)\n",
    "        return ft[result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        \n",
    "        def countEval(s, result, memo):\n",
    "            if len(s) == 0: return 0\n",
    "            if len(s) == 1: return 1 if int(s) == result else 0\n",
    "            if (result, s) in memo: return memo[(result, s)]\n",
    "\n",
    "            res = 0\n",
    "            for i, c in enumerate(s):\n",
    "                if c not in \"&|^\": continue\n",
    "                leftFalse = countEval(s[:i], 0, memo)\n",
    "                leftTrue = countEval(s[:i], 1, memo)\n",
    "                rightFalse = countEval(s[i+1:], 0, memo)\n",
    "                rightTrue = countEval(s[i+1:], 1, memo)\n",
    "\n",
    "                if c == '|' and result:\n",
    "                    res += leftFalse * rightTrue + leftTrue * rightFalse + leftTrue * rightTrue\n",
    "                elif c == '|' and not result:\n",
    "                    res += leftFalse * rightFalse\n",
    "                elif c == '&' and result:\n",
    "                    res += leftTrue * rightTrue\n",
    "                elif c == '&' and not result:\n",
    "                    res += leftFalse * rightTrue + leftTrue * rightFalse + leftFalse * rightFalse\n",
    "                elif c == '^' and result:\n",
    "                    res += leftFalse * rightTrue + leftTrue * rightFalse\n",
    "                elif c == '^' and not result:\n",
    "                    res += leftFalse * rightFalse + leftTrue * rightTrue\n",
    "            \n",
    "            memo[(result, s)] = res\n",
    "            return res\n",
    "\n",
    "        return countEval(s, result, {})       \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cal(self, a, b, opt) -> int:\n",
    "        a = int(a)\n",
    "        b = int(b)\n",
    "        if opt == '&': return a & b\n",
    "        if opt == '|': return a | b\n",
    "        if opt == '^': return a ^ b\n",
    "\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        n = len(s) // 2 + 1\n",
    "        dp = [[[0] * 2 for j in range(n)] for i in range(n)]\n",
    "\n",
    "        for rg in range(n):\n",
    "            for i in range(n):\n",
    "                j = i + rg\n",
    "                if j >= n: continue\n",
    "                if i == j:\n",
    "                    dp[i][j][0] = int(s[i * 2] == '0')\n",
    "                    dp[i][j][1] = int(s[i * 2] == '1')\n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        for ch1 in (0, 1):\n",
    "                            for ch2 in (0, 1):\n",
    "                                dp[i][j][self.cal(ch1, ch2, s[k * 2 + 1])] += dp[i][k][ch1] * dp[k + 1][j][ch2]\n",
    "\n",
    "        return dp[0][n - 1][result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        dp = [[[0] * 2 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        if len(s) < 1:\n",
    "            return 0\n",
    "        if len(s) < 2:\n",
    "            if int(s[0]) == result:\n",
    "                return 1 \n",
    "            else:\n",
    "                return 0 \n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i][i][0] = 1 \n",
    "            else:\n",
    "                dp[i][i][1] = 1 \n",
    "\n",
    "        for length in range(2, len(s), 2):\n",
    "            for i in range(0, len(s)-length, 2):\n",
    "                j = i + length\n",
    "                for k in range(i+1, j, 2):\n",
    "                    if s[k] == '&':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + \\\n",
    "                                    dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1]\n",
    "                    elif s[k] == '|':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                    elif s[k] == '^':\n",
    "                        dp[i][j][0] += dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0] \n",
    "                    \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        if len(s) < 3: return int(int(s[0]) == result)\n",
    "        n = (len(s) - 1) // 2\n",
    "        f = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        def calc(a, b, op):\n",
    "            if op == '&': return a & b\n",
    "            if op == '|': return a | b\n",
    "            if op == '^': return a ^ b\n",
    "\n",
    "        for le in range(1, n + 1):\n",
    "            for l in range(1, n - le + 2):\n",
    "                r = l + le - 1\n",
    "                if le == 1: \n",
    "                    idx = 2 * l - 1\n",
    "                    c = calc(int(s[idx - 1]), int(s[idx + 1]), s[idx])\n",
    "                    f[l][r][c] = 1\n",
    "                    continue\n",
    "                for k in range(l, r + 1):\n",
    "                    idx = 2 * k - 1\n",
    "                    if k == l:\n",
    "                        a = int(s[idx - 1])\n",
    "                        for b in range(2):\n",
    "                            c = calc(a, b, s[idx])\n",
    "                            f[l][r][c] +=  f[k + 1][r][b]\n",
    "                    elif k == r:\n",
    "                        b = int(s[idx + 1])\n",
    "                        for a in range(2):\n",
    "                            c = calc(a, b, s[idx])\n",
    "                            f[l][r][c] += f[l][k - 1][a]\n",
    "                    else:\n",
    "                        for a in range(2):\n",
    "                            for b in range(2):\n",
    "                                c = calc(a, b, s[idx])\n",
    "                                f[l][r][c] += f[l][k - 1][a] * f[k + 1][r][b]\n",
    "\n",
    "        return f[1][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1 if int(s[0]) == result else 0\n",
    "        dp = [[[0]*2 for _ in range(n)] for _ in range(n)]\n",
    "        # base case\n",
    "        for i in range(n):\n",
    "            if s[i] == \"1\" or s[i] == \"0\":\n",
    "                dp[i][i][int(s[i])] = 1\n",
    "        # 套区间dp模板\n",
    "        # 枚举区间长度len，跳步为2，一个数字一个符号\n",
    "        for length in range(2,n+1,2):\n",
    "            # 枚举区间起点，数字位，跳步为2\n",
    "            for i in range(0,n-length+1,2):\n",
    "                # 区间终点，数字位\n",
    "                j = i+length\n",
    "                # 枚举分割点，三种 '&', '|', '^'，跳步为2\n",
    "                for k in range(i+1,j,2):\n",
    "                    if s[k] == \"&\":\n",
    "                    # 结果为0 有三种情况： 0 0, 0 1, 1 0\n",
    "                    # 结果为1 有一种情况： 1 1\n",
    "                        dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][1]\n",
    "                    if s[k] ==\"|\":\n",
    "                        # 结果为0 有一种情况： 0 0\n",
    "                        # 结果为1 有三种情况： 0 1, 1 0, 1 1\n",
    "                        dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][1] * dp[k + 1][j][1]\n",
    "                    if s[k] == \"^\":\n",
    "                        # 结果为0 有两种情况： 0 0, 1 1\n",
    "                        # 结果为1 有两种情况： 0 1, 1 0\n",
    "                        dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][1] * dp[k + 1][j][1]\n",
    "                        dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1]\n",
    "        return dp[0][n - 1][result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.f = {}\n",
    "        return self.search(s, 0, len(s) - 1, result)\n",
    "\n",
    "    def search(self, s: str, left: int, right: int, result: int) -> int:\n",
    "        if left == right:\n",
    "            return 1 if int(s[left]) == result else 0\n",
    "        key = (left, right, result)\n",
    "        if key in self.f:\n",
    "            return self.f[key]\n",
    "        num_ways = 0\n",
    "        for i in range(left + 1, right):\n",
    "            if s[i].isdigit():\n",
    "                continue\n",
    "            l0 = self.search(s, left, i - 1, 0)\n",
    "            l1 = self.search(s, left, i - 1, 1)\n",
    "            r0 = self.search(s, i + 1, right, 0)\n",
    "            r1 = self.search(s, i + 1, right, 1)\n",
    "            if s[i] == \"&\":\n",
    "                if result == 1:\n",
    "                    num_ways += l1 * r1\n",
    "                else:\n",
    "                    num_ways += l0 * r0 + l0 * r1 + l1 * r0\n",
    "            elif s[i] == \"|\":\n",
    "                if result == 0:\n",
    "                    num_ways += l0 * r0\n",
    "                else:\n",
    "                    num_ways += l0 * r1 + l1 * r1 + l1 * r0\n",
    "            else:\n",
    "                if result == 0:\n",
    "                    num_ways += l0 * r0 + l1 * r1\n",
    "                else:\n",
    "                    num_ways += l0 * r1 + l1 * r0\n",
    "        self.f[key] = num_ways\n",
    "        return num_ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        n = len(s) \n",
    "        dp = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]\n",
    "        # 初始化\n",
    "        for i in range(0,n,2):\n",
    "            if s[i] == '0':\n",
    "                dp[i][i][0] = 1\n",
    "            elif s[i] == '1':\n",
    "                dp[i][i][1] = 1\n",
    "\n",
    "        for length in range(2, n+1, 2):\n",
    "            for start in range(0, n+1-length, 2):\n",
    "                end = start + length\n",
    "                for op in range(start+1, end, 2):\n",
    "                    if s[op] == '^':\n",
    "                        dp[start][end][0] += dp[start][op-1][1]*dp[op+1][end][1] + dp[start][op-1][0]*dp[op+1][end][0]\n",
    "                        dp[start][end][1] += dp[start][op-1][1]*dp[op+1][end][0] + dp[start][op-1][0]*dp[op+1][end][1]\n",
    "                    if s[op] == '&':\n",
    "                        dp[start][end][0] += dp[start][op-1][0]*dp[op+1][end][1] + dp[start][op-1][1]*dp[op+1][end][0] + dp[start][op-1][0]*dp[op+1][end][0]\n",
    "                        dp[start][end][1] += dp[start][op-1][1]*dp[op+1][end][1]\n",
    "                    if s[op] == '|':\n",
    "                        dp[start][end][1] += dp[start][op-1][0]*dp[op+1][end][1] + dp[start][op-1][1]*dp[op+1][end][0] + dp[start][op-1][1]*dp[op+1][end][1]\n",
    "                        dp[start][end][0] += dp[start][op-1][0]*dp[op+1][end][0]\n",
    "        \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        # dp——还是非常有趣的！\n",
    "        def get(op,t1,t2):\n",
    "            if op == \"^\":\n",
    "                return t1 ^ t2\n",
    "            elif op == \"|\":\n",
    "                return t1 | t2\n",
    "            else:\n",
    "                return t1 & t2\n",
    "\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            if int(s) == result:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        m = n // 2\n",
    "        dp = [[[0]*2 for _ in range(m)] for _ in range(m)]\n",
    "        for lenth in range(1,m+1):\n",
    "            i = 0\n",
    "            while i+lenth-1 < m:\n",
    "                j = i + lenth - 1\n",
    "                if lenth == 1:\n",
    "                    t = i *2\n",
    "                    dp[i][j][get(s[t+1],int(s[t]),int(s[t+2]))] = 1\n",
    "                else:\n",
    "                    for k in range(i,j+1):\n",
    "                        t = k * 2\n",
    "                        if k == i:\n",
    "                            if dp[k+1][j][0]:\n",
    "                                dp[i][j][get(s[t+1],int(s[t]),0)] += dp[k+1][j][0]\n",
    "                            if dp[k + 1][j][1]:\n",
    "                                dp[i][j][get(s[t + 1], int(s[t]), 1)] += dp[k + 1][j][1]\n",
    "                        elif k == j:\n",
    "                            if dp[i][k-1][0]:\n",
    "                                dp[i][j][get(s[t + 1], int(s[t+2]), 0)] += dp[i][k-1][0]\n",
    "                            if dp[i][k-1][1]:\n",
    "                                dp[i][j][get(s[t + 1], int(s[t+2]), 1)] += dp[i][k-1][1]\n",
    "                        else:\n",
    "                            if dp[i][k-1][0] and dp[k+1][j][0]:\n",
    "                                dp[i][j][get(s[t + 1], 0, 0)] += dp[i][k-1][0] * dp[k + 1][j][0]\n",
    "                            if dp[i][k-1][0] and dp[k+1][j][1]:\n",
    "                                dp[i][j][get(s[t + 1], 0, 1)] += dp[i][k-1][0] * dp[k + 1][j][1]\n",
    "                            if dp[i][k-1][1] and dp[k+1][j][0]:\n",
    "                                dp[i][j][get(s[t + 1], 1, 0)] += dp[i][k-1][1] * dp[k + 1][j][0]\n",
    "                            if dp[i][k-1][1] and dp[k+1][j][1]:\n",
    "                                dp[i][j][get(s[t + 1], 1, 1)] += dp[i][k-1][1] * dp[k + 1][j][1]\n",
    "                i += 1\n",
    "        return dp[0][m-1][result]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        n = (len(s)//2)+1\n",
    "        num_list = [int(c) for c in s if c=='1' or c=='0']\n",
    "        oper_list = [c for c in s if c!='1' and c!='0']\n",
    "        dp = [[[0]*2 for _ in range(n)] for _ in range(n)]\n",
    "        # dp[i][j]表示[i,j]的数字得到结果0和1分别有多少种方案\n",
    "        # 区间DP\n",
    "        for i in range(n):\n",
    "            if num_list[i] == 1:\n",
    "                dp[i][i][0], dp[i][i][1] = 0, 1\n",
    "            else:\n",
    "                dp[i][i][0], dp[i][i][1] = 1, 0\n",
    "        for L in range(2,n+1):\n",
    "            for i in range(n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                for k in range(l,r):\n",
    "                    left_zero, left_one = dp[l][k][0], dp[l][k][1]\n",
    "                    right_zero, right_one = dp[k+1][r][0], dp[k+1][r][1]\n",
    "                    oper = oper_list[k]\n",
    "                    if oper == '&':\n",
    "                        dp[l][r][0] += (left_zero*right_zero + left_zero*right_one + left_one*right_zero)\n",
    "                        dp[l][r][1] += (left_one*right_one)\n",
    "                    elif oper == '|':\n",
    "                        dp[l][r][0] += (left_zero*right_zero)\n",
    "                        dp[l][r][1] += (left_one*right_one + left_zero*right_one + left_one*right_zero)\n",
    "                    else:\n",
    "                        dp[l][r][0] += (left_zero*right_zero + left_one*right_one)\n",
    "                        dp[l][r][1] += (left_one*right_zero + left_zero*right_one)\n",
    "            pass\n",
    "        return dp[0][n-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        dp = [[[0] * 2 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        if len(s) < 1:\n",
    "            return 0\n",
    "        if len(s) < 2:\n",
    "            if int(s[0]) == result:\n",
    "                return 1 \n",
    "            else:\n",
    "                return 0 \n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i][i][0] = 1 \n",
    "            else:\n",
    "                dp[i][i][1] = 1 \n",
    "\n",
    "        for length in range(2, len(s), 2):\n",
    "            for i in range(0, len(s)-length, 2):\n",
    "                j = i + length\n",
    "                for k in range(i+1, j, 2):\n",
    "                    if s[k] == '&':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + \\\n",
    "                                    dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1]\n",
    "                    elif s[k] == '|':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                    elif s[k] == '^':\n",
    "                        dp[i][j][0] += dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0] \n",
    "                    \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "#         logic_dict = {\"1&1\": \"1\", \"1|1\": \"1\", \"1^1\": \"0\",\n",
    "#                      \"0&1\": \"0\", \"0|1\": \"1\", \"0^1\": \"1\",\n",
    "#                      \"1&0\": \"0\", \"1|0\": \"1\", \"1^0\": \"1\",\n",
    "#                      \"0&0\": \"0\", \"0|0\": \"0\", \"0^0\": \"0\"}\n",
    "#         if len(s) == 1:\n",
    "#             return 1 if int(s) == result else 0\n",
    "        \n",
    "#         self.count = {}\n",
    "#         def help(s0, path):\n",
    "#             if s0 in logic_dict:\n",
    "#                 if int(logic_dict[s0]) == result:\n",
    "#                     path = \"\".join(path)\n",
    "#                     if path not in self.count:\n",
    "#                         self.count[path] = 0\n",
    "#                     self.count[path] += 1\n",
    "#                 return\n",
    "            \n",
    "#             for i in range(1, len(s0), 2):\n",
    "#                 new_s0 = s0[:i-1] + logic_dict[s0[i-1:i+2]] + s0[i+2:]\n",
    "#                 new_path = path[:i-1] + [\"(\" + \"\".join(path[i-1:i+2]) + \")\"] + path[i+2:]\n",
    "#                 help(new_s0, new_path)\n",
    "        \n",
    "#         help(s, list(s))\n",
    "#         return len(self.count.keys())\n",
    "        @functools.lru_cache()\n",
    "        def dfs(s):\n",
    "            count = [0] * 2\n",
    "            if s in '01':\n",
    "                count[int(s)] = 1\n",
    "                return count\n",
    "            for i, c in enumerate(s):\n",
    "                if c not in '01':\n",
    "                    left = dfs(s[:i])\n",
    "                    right = dfs(s[i+1:])\n",
    "                    for li, lv in enumerate(left):\n",
    "                        for ri, rv in enumerate(right):\n",
    "                            if c == '|':\n",
    "                                r = li | ri\n",
    "                            if c == '&':\n",
    "                                r = li & ri\n",
    "                            if c == '^':\n",
    "                                r = li ^ ri\n",
    "                            count[r] += lv * rv\n",
    "            return count\n",
    "        return dfs(s)[result]\n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        dp = [[[0, 0] for _ in range(len(s) // 2 + 1)] for _ in range(len(s) // 2 + 1)]\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][i][int(s[i*2]) - 0] = 1\n",
    "        for i in range(len(dp)-2, -1, -1):\n",
    "            for j in range(i+1, len(dp)):\n",
    "                for k in range(i, j):\n",
    "                    if s[k*2+1] == '&':\n",
    "                        dp[i][j][0] += dp[i][k][0] * dp[k+1][j][0] + dp[i][k][0] * dp[k+1][j][1] + dp[i][k][1] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k][1] * dp[k+1][j][1]\n",
    "                        continue\n",
    "                    if s[k*2+1] == '|':\n",
    "                        dp[i][j][0] += dp[i][k][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k][1] * dp[k+1][j][1] + dp[i][k][0] * dp[k+1][j][1] + dp[i][k][1] * dp[k+1][j][0]\n",
    "                    if s[k*2+1] == '^':\n",
    "                        dp[i][j][0] += dp[i][k][1] * dp[k+1][j][1] + dp[i][k][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k][0] * dp[k+1][j][1] + dp[i][k][1] * dp[k+1][j][0]                \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        \"\"\"\n",
    "        {\n",
    "            符号: {\n",
    "                需要计算出的结果: {\n",
    "                    [(左子式需要计算的结果，右子式需要计算的结果)]\n",
    "                }\n",
    "            }\n",
    "            \n",
    "        }\n",
    "        \"\"\"\n",
    "        self.ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s, result, {})\n",
    "        \n",
    "    def dfs(self, expression, result, memo):\n",
    "        # 查询备忘录，有结果则直接返回\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "        \n",
    "        # 边界情况\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(bool(val) == result)\n",
    "        \n",
    "        # 递归计算左右子式的结果\n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr, rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[:i], lr, memo)*self.dfs(expression[i+1:], rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        \"\"\"\n",
    "        {\n",
    "            符号: {\n",
    "                需要计算出的结果: {\n",
    "                    [(左子式需要计算的结果，右子式需要计算的结果)]\n",
    "                }\n",
    "            }\n",
    "            \n",
    "        }\n",
    "        \"\"\"\n",
    "        self.ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s, result, {})\n",
    "        \n",
    "    def dfs(self, expression, result, memo):\n",
    "        # 查询备忘录，有结果则直接返回\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "        \n",
    "        # 边界情况\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(bool(val) == result)\n",
    "        \n",
    "        # 递归计算左右子式的结果\n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr, rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[:i], lr, memo)*self.dfs(expression[i+1:], rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        \"\"\"\n",
    "        {\n",
    "            符号: {\n",
    "                需要计算出的结果: {\n",
    "                    [(左子式需要计算的结果，右子式需要计算的结果)]\n",
    "                }\n",
    "            }\n",
    "            \n",
    "        }\n",
    "        \"\"\"\n",
    "        self.ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "        return self.dfs(s, result, {})\n",
    "        \n",
    "    def dfs(self, expression, result, memo):\n",
    "        # 查询备忘录，有结果则直接返回\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "        \n",
    "        # 边界情况\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(bool(val) == result)\n",
    "        \n",
    "        # 递归计算左右子式的结果\n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr, rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[:i], lr, memo)*self.dfs(expression[i+1:], rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.ops = {\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            },\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, True), (True, False), (False, True)],\n",
    "                False: [(False, False)]\n",
    "            }\n",
    "        }\n",
    "\n",
    "        return self.dfs(s, result, {})\n",
    "    \n",
    "    def dfs(self, expression, result, memo):\n",
    "        if (expression, result) in memo:\n",
    "            return memo[(expression, result)]\n",
    "\n",
    "        if len(expression) == 1:\n",
    "            val = int(expression)\n",
    "            return int(bool(val) == result)\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in self.ops:\n",
    "                for lr, rr in self.ops[expression[i]][result]:\n",
    "                    total += self.dfs(expression[: i], lr, memo) \\\n",
    "                             * self.dfs(expression[i+1:], rr, memo)\n",
    "        memo[(expression, result)] = total\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        @cache\n",
    "        def dfs(l, r, target):\n",
    "            if l == r: return int(int(s[l]) == target)\n",
    "            ans = 0\n",
    "            for i in range(l + 1, r, 2):\n",
    "                l0, l1, r0, r1 = dfs(l, i - 1, 0), dfs(l, i - 1, 1), dfs(i + 1, r, 0), dfs(i + 1, r, 1)\n",
    "                if s[i] == '^':\n",
    "                    if target: ans += l0 * r1 + l1 * r0\n",
    "                    else: ans += l0 * r0 + l1 * r1\n",
    "                elif s[i] == '|':\n",
    "                    if target: ans += l0 * r1 + l1 * r0 + l1 * r1\n",
    "                    else: ans += l0 * r0\n",
    "                else:\n",
    "                    if target: ans += l1 * r1\n",
    "                    else: ans += l0 * r0 + l0 * r1 + l1 * r0\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, len(s) - 1, result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        n = (len(s)//2)+1\n",
    "        num_list = [int(c) for c in s if c=='1' or c=='0']\n",
    "        oper_list = [c for c in s if c!='1' and c!='0']\n",
    "        dp = [[[0]*2 for _ in range(n)] for _ in range(n)]\n",
    "        # dp[i][j]表示[i,j]的数字得到结果0和1分别有多少种方案\n",
    "        for i in range(n):\n",
    "            if num_list[i] == 1:\n",
    "                dp[i][i][0], dp[i][i][1] = 0, 1\n",
    "            else:\n",
    "                dp[i][i][0], dp[i][i][1] = 1, 0\n",
    "        for L in range(2,n+1):\n",
    "            for i in range(n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                for k in range(l,r):\n",
    "                    left_zero, left_one = dp[l][k][0], dp[l][k][1]\n",
    "                    right_zero, right_one = dp[k+1][r][0], dp[k+1][r][1]\n",
    "                    oper = oper_list[k]\n",
    "                    if oper == '&':\n",
    "                        dp[l][r][0] += (left_zero*right_zero + left_zero*right_one + left_one*right_zero)\n",
    "                        dp[l][r][1] += (left_one*right_one)\n",
    "                    elif oper == '|':\n",
    "                        dp[l][r][0] += (left_zero*right_zero)\n",
    "                        dp[l][r][1] += (left_one*right_one + left_zero*right_one + left_one*right_zero)\n",
    "                    else:\n",
    "                        dp[l][r][0] += (left_zero*right_zero + left_one*right_one)\n",
    "                        dp[l][r][1] += (left_one*right_zero + left_zero*right_one)\n",
    "            pass\n",
    "        return dp[0][n-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        ops = {'|': or_, '^': xor, '&': and_}\n",
    "\n",
    "        memory = collections.defaultdict(collections.Counter)\n",
    "        memory[\"0\"][0] = 1\n",
    "        memory[\"1\"][1] = 1\n",
    "\n",
    "        def get_count(s):\n",
    "            if s not in memory:\n",
    "                for i in range(1, len(s), 2): \n",
    "                    for a1, cnt1 in get_count(s[:i]).items():                      \n",
    "                        for a2, cnt2 in get_count(s[i + 1:]).items():               \n",
    "                            memory[s][ops[s[i]](a1, a2)] += cnt1 * cnt2             \n",
    "            return memory[s]\n",
    "\n",
    "        return get_count(s)[result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        length = len(s)\n",
    "        dp_array = [[[0, 0] for i in range(length)] for i in range(length)]\n",
    "        for i in range(0, length, 2):\n",
    "            if s[i] == \"0\" or s[i] == \"1\":\n",
    "                dp_array[i][i][int(s[i])] = 1\n",
    "        # print(dp_array)\n",
    "        for l in range(2, length, 2): #区间长度\n",
    "            for start in range(0, length-l, 2): #区间起始点\n",
    "                end = start + l #区间结束点\n",
    "                for i in range(start+1, end, 2): #切分点\n",
    "                    if s[i] == \"&\":\n",
    "                        dp_array[start][end][0] += dp_array[start][i-1][0]*dp_array[i+1][end][0] + dp_array[start][i-1][0]*dp_array[i+1][end][1] + dp_array[start][i-1][1]*dp_array[i+1][end][0]\n",
    "                        dp_array[start][end][1] += dp_array[start][i-1][1]*dp_array[i+1][end][1]\n",
    "                    elif s[i] == \"|\":\n",
    "                        dp_array[start][end][0] += dp_array[start][i-1][0]*dp_array[i+1][end][0]\n",
    "                        dp_array[start][end][1] += dp_array[start][i-1][1]*dp_array[i+1][end][1] + dp_array[start][i-1][0]*dp_array[i+1][end][1] + dp_array[start][i-1][1]*dp_array[i+1][end][0]\n",
    "                    elif s[i] == \"^\":\n",
    "                        dp_array[start][end][0] += dp_array[start][i-1][0]*dp_array[i+1][end][0] +  dp_array[start][i-1][1]*dp_array[i+1][end][1]\n",
    "                        dp_array[start][end][1] += dp_array[start][i-1][1]*dp_array[i+1][end][0] + dp_array[start][i-1][0]*dp_array[i+1][end][1]\n",
    "        return dp_array[0][length-1][result]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        dp = [[[0] * 2 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        if len(s) < 1:\n",
    "            return 0\n",
    "        if len(s) < 2:\n",
    "            if int(s[0]) == result:\n",
    "                return 1 \n",
    "            else:\n",
    "                return 0 \n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i][i][0] = 1 \n",
    "            else:\n",
    "                dp[i][i][1] = 1 \n",
    "\n",
    "        for length in range(2, len(s), 2):\n",
    "            for i in range(0, len(s)-length, 2):\n",
    "                j = i + length\n",
    "                for k in range(i+1, j, 2):\n",
    "                    if s[k] == '&':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + \\\n",
    "                                    dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1]\n",
    "                    elif s[k] == '|':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                    elif s[k] == '^':\n",
    "                        dp[i][j][0] += dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0] \n",
    "                    \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        acc = {\n",
    "            '1&1':'1','1&0':'0','0&1':'0','0&0':'0',\n",
    "            '1|1':'1','1|0':'1','0|1':'1','0|0':'0',\n",
    "            '1^1':'0','1^0':'1','0^1':'1','0^0':'0',\n",
    "        }\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            n = len(s)\n",
    "            if n==1:\n",
    "                return {'0':int(s=='0'),'1':int(s=='1')}\n",
    "            res = {'0':0,'1':0}\n",
    "            for i in range(1,n,2):\n",
    "                left = dfs(s[:i])\n",
    "                right = dfs(s[i+1:])\n",
    "                res[acc['0'+s[i]+'0']]+=left['0']*right['0']\n",
    "                res[acc['1'+s[i]+'0']]+=left['1']*right['0']\n",
    "                res[acc['0'+s[i]+'1']]+=left['0']*right['1']\n",
    "                res[acc['1'+s[i]+'1']]+=left['1']*right['1']\n",
    "            return res\n",
    "        res = dfs(s)\n",
    "        return res[str(result)]\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        acc = {\n",
    "            '1&1':'1','1&0':'0','0&1':'0','0&0':'0',\n",
    "            '1|1':'1','1|0':'1','0|1':'1','0|0':'0',\n",
    "            '1^1':'0','1^0':'1','0^1':'1','0^0':'0',\n",
    "        }\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            n = len(s)\n",
    "            if n==1:\n",
    "                return {'0':int(s=='0'),'1':int(s=='1')}\n",
    "            res = {'0':0,'1':0}\n",
    "            for i in range(1,n,2):\n",
    "                left = dfs(s[:i])\n",
    "                right = dfs(s[i+1:])\n",
    "                res[acc['0'+s[i]+'0']]+=left['0']*right['0']\n",
    "                res[acc['1'+s[i]+'0']]+=left['1']*right['0']\n",
    "                res[acc['0'+s[i]+'1']]+=left['0']*right['1']\n",
    "                res[acc['1'+s[i]+'1']]+=left['1']*right['1']\n",
    "            return res\n",
    "        res = dfs(s)\n",
    "        return res[str(result)]\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        dp = [[[0] * 2 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        if len(s) < 1:\n",
    "            return 0\n",
    "        if len(s) < 2:\n",
    "            if int(s[0]) == result:\n",
    "                return 1 \n",
    "            else:\n",
    "                return 0 \n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i][i][0] = 1 \n",
    "            else:\n",
    "                dp[i][i][1] = 1 \n",
    "\n",
    "        for length in range(2, len(s), 2):\n",
    "            for i in range(0, len(s)-length, 2):\n",
    "                j = i + length\n",
    "                for k in range(i+1, j, 2):\n",
    "                    if s[k] == '&':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + \\\n",
    "                                    dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1]\n",
    "                    elif s[k] == '|':\n",
    "                        dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][1]\n",
    "                    elif s[k] == '^':\n",
    "                        dp[i][j][0] += dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][0]\n",
    "                        dp[i][j][1] += dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0] \n",
    "                    \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, l, r):\n",
    "        #print(l, r)\n",
    "        if self.mem[l][r] != -1:\n",
    "            return self.mem[l][r]\n",
    "\n",
    "        if l == r:\n",
    "            if self.s[l] == '1':\n",
    "                print(l, r, [1, 0])\n",
    "                self.mem[l][r] = [1, 0]\n",
    "                return [1, 0]\n",
    "            else:\n",
    "                print(l, r, [0, 1])\n",
    "                self.mem[l][r] = [0, 1]\n",
    "                return [0, 1]\n",
    "\n",
    "        ans = [0, 0]\n",
    "        for k in range(l, r, 2):\n",
    "            left = self.process(l , k)\n",
    "            right = self.process(k + 2, r)\n",
    "\n",
    "            if self.s[k + 1] == '&':\n",
    "                if l == 0 and r == 4:\n",
    "                    print(ans[0], ans[1], k)\n",
    "                ans[0] += left[0] * right[0]\n",
    "                ans[1] += left[0] * right[1] + left[1] * right[0] + left[1] * right[1]\n",
    "            elif self.s[k + 1] == '|':\n",
    "                if l == 0 and r == 4:\n",
    "                    print(ans[0], ans[1], k)\n",
    "                ans[0] += left[0] * right[0] + left[0] * right[1] + left[1] * right[0]\n",
    "                ans[1] += left[1] * right[1]\n",
    "                if l == 0 and r == 4:\n",
    "                    print(ans[0], ans[1], k)\n",
    "            else:\n",
    "                ans[0] += left[0] * right[1] + left[1] * right[0]\n",
    "                ans[1] += left[0] * right[0] + left[1] * right[1]\n",
    "\n",
    "        self.mem[l][r] = ans\n",
    "        print(l, r, ans)\n",
    "        return ans\n",
    "\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.s = s\n",
    "        length = len(s)\n",
    "        #print(length)\n",
    "\n",
    "        self.mem = []\n",
    "\n",
    "        for i in range(0, length):\n",
    "            self.mem.append([])\n",
    "            for j in range(0, length):\n",
    "                self.mem[i].append(-1)\n",
    "\n",
    "        ans = self.process(0, length - 1)\n",
    "\n",
    "        if result:\n",
    "            return ans[0]\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        acc = {\n",
    "            '1&1':'1','1&0':'0','0&1':'0','0&0':'0',\n",
    "            '1|1':'1','1|0':'1','0|1':'1','0|0':'0',\n",
    "            '1^1':'0','1^0':'1','0^1':'1','0^0':'0',\n",
    "        }\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            n = len(s)\n",
    "            if n==1:\n",
    "                return {'0':int(s=='0'),'1':int(s=='1')}\n",
    "            res = {'0':0,'1':0}\n",
    "            for i in range(1,n,2):\n",
    "                left = dfs(s[:i])\n",
    "                right = dfs(s[i+1:])\n",
    "                res[acc['0'+s[i]+'0']]+=left['0']*right['0']\n",
    "                res[acc['1'+s[i]+'0']]+=left['1']*right['0']\n",
    "                res[acc['0'+s[i]+'1']]+=left['0']*right['1']\n",
    "                res[acc['1'+s[i]+'1']]+=left['1']*right['1']\n",
    "            return res\n",
    "        res = dfs(s)\n",
    "        return res[str(result)]\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        n = len(s) \n",
    "        dp = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]\n",
    "        # 初始化\n",
    "        for i in range(0,n,2):\n",
    "            if s[i] == '0':\n",
    "                dp[i][i][0] = 1\n",
    "            elif s[i] == '1':\n",
    "                dp[i][i][1] = 1\n",
    "\n",
    "        for length in range(2, n+1, 2):\n",
    "            for start in range(0, n+1-length, 2):\n",
    "                end = start + length\n",
    "                for op in range(start+1, end, 2):\n",
    "                    if s[op] == '^':\n",
    "                        dp[start][end][0] += dp[start][op-1][1]*dp[op+1][end][1] + dp[start][op-1][0]*dp[op+1][end][0]\n",
    "                        dp[start][end][1] += dp[start][op-1][1]*dp[op+1][end][0] + dp[start][op-1][0]*dp[op+1][end][1]\n",
    "                    if s[op] == '&':\n",
    "                        dp[start][end][0] += dp[start][op-1][0]*dp[op+1][end][1] + dp[start][op-1][1]*dp[op+1][end][0] + dp[start][op-1][0]*dp[op+1][end][0]\n",
    "                        dp[start][end][1] += dp[start][op-1][1]*dp[op+1][end][1]\n",
    "                    if s[op] == '|':\n",
    "                        dp[start][end][1] += dp[start][op-1][0]*dp[op+1][end][1] + dp[start][op-1][1]*dp[op+1][end][0] + dp[start][op-1][1]*dp[op+1][end][1]\n",
    "                        dp[start][end][0] += dp[start][op-1][0]*dp[op+1][end][0]\n",
    "        \n",
    "        return dp[0][-1][result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, l, r):\n",
    "        #print(l, r)\n",
    "        if self.mem[l][r] != -1:\n",
    "            return self.mem[l][r]\n",
    "\n",
    "        if l == r:\n",
    "            if self.s[l] == '1':\n",
    "                print(l, r, [1, 0])\n",
    "                self.mem[l][r] = [1, 0]\n",
    "                return [1, 0]\n",
    "            else:\n",
    "                print(l, r, [0, 1])\n",
    "                self.mem[l][r] = [0, 1]\n",
    "                return [0, 1]\n",
    "\n",
    "        ans = [0, 0]\n",
    "        for k in range(l, r, 2):\n",
    "            left = self.process(l , k)\n",
    "            right = self.process(k + 2, r)\n",
    "\n",
    "            #print(k)\n",
    "            if self.s[k + 1] == '&':\n",
    "                if l == 0 and r == 4:\n",
    "                    print(ans[0], ans[1], k)\n",
    "                ans[0] += left[0] * right[0]\n",
    "                ans[1] += left[0] * right[1] + left[1] * right[0] + left[1] * right[1]\n",
    "                #if l == 0 and r == 4:\n",
    "                    #print(ans[0], ans[1], k, left[0], left[1], right[0], right[1],left[0] * right[1] + left[1] * right[0] + left[1] * left[1])\n",
    "            elif self.s[k + 1] == '|':\n",
    "                if l == 0 and r == 4:\n",
    "                    print(ans[0], ans[1], k)\n",
    "                ans[0] += left[0] * right[0] + left[0] * right[1] + left[1] * right[0]\n",
    "                ans[1] += left[1] * right[1]\n",
    "                if l == 0 and r == 4:\n",
    "                    print(ans[0], ans[1], k)\n",
    "            else:\n",
    "                ans[0] += left[0] * right[1] + left[1] * right[0]\n",
    "                ans[1] += left[0] * right[0] + left[1] * right[1]\n",
    "\n",
    "        self.mem[l][r] = ans\n",
    "        print(l, r, ans)\n",
    "        return ans\n",
    "\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        self.s = s\n",
    "        length = len(s)\n",
    "        #print(length)\n",
    "\n",
    "        self.mem = []\n",
    "\n",
    "        for i in range(0, length):\n",
    "            self.mem.append([])\n",
    "            for j in range(0, length):\n",
    "                self.mem[i].append(-1)\n",
    "\n",
    "        ans = self.process(0, length - 1)\n",
    "\n",
    "        if result:\n",
    "            return ans[0]\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, target_bool: bool):\n",
    "            if i + 1 == j:\n",
    "                return int(bool(int(s[i])) == target_bool)\n",
    "            total = 0\n",
    "            for k in range(i, j):\n",
    "                if s[k] in list(\"&|^\"):\n",
    "                    for need_left, need_right in ops[s[k]][target_bool]:\n",
    "                        total += dfs(i, k, need_left) * dfs(k + 1, j, need_right)\n",
    "            \n",
    "            return total\n",
    "        \n",
    "        return dfs(0, len(s), result)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        acc = {\n",
    "            '1&1':'1','1&0':'0','0&1':'0','0&0':'0',\n",
    "            '1|1':'1','1|0':'1','0|1':'1','0|0':'0',\n",
    "            '1^1':'0','1^0':'1','0^1':'1','0^0':'0',\n",
    "        }\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            n = len(s)\n",
    "            if n==1:\n",
    "                return {'0':int(s=='0'),'1':int(s=='1')}\n",
    "            res = {'0':0,'1':0}\n",
    "            for i in range(1,n,2):\n",
    "                left = dfs(s[:i])\n",
    "                right = dfs(s[i+1:])\n",
    "                res[acc['0'+s[i]+'0']]+=left['0']*right['0']\n",
    "                res[acc['1'+s[i]+'0']]+=left['1']*right['0']\n",
    "                res[acc['0'+s[i]+'1']]+=left['0']*right['1']\n",
    "                res[acc['1'+s[i]+'1']]+=left['1']*right['1']\n",
    "            return res\n",
    "        res = dfs(s)\n",
    "        return res[str(result)]\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        acc = {\n",
    "            '1&1':'1','1&0':'0','0&1':'0','0&0':'0',\n",
    "            '1|1':'1','1|0':'1','0|1':'1','0|0':'0',\n",
    "            '1^1':'0','1^0':'1','0^1':'1','0^0':'0',\n",
    "        }\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            n = len(s)\n",
    "            if n==1:\n",
    "                return {'0':int(s=='0'),'1':int(s=='1')}\n",
    "            res = {'0':0,'1':0}\n",
    "            for i in range(1,n,2):\n",
    "                left = dfs(s[:i])\n",
    "                right = dfs(s[i+1:])\n",
    "                res[acc['0'+s[i]+'0']]+=left['0']*right['0']\n",
    "                res[acc['1'+s[i]+'0']]+=left['1']*right['0']\n",
    "                res[acc['0'+s[i]+'1']]+=left['0']*right['1']\n",
    "                res[acc['1'+s[i]+'1']]+=left['1']*right['1']\n",
    "            return res\n",
    "        res = dfs(s)\n",
    "        return res[str(result)]\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s, result):\n",
    "        @functools.lru_cache()\n",
    "        def dfs(s):\n",
    "            count = [0] * 2\n",
    "            if s in '01':\n",
    "                count[int(s)] = 1\n",
    "                return count\n",
    "            for i, c in enumerate(s):\n",
    "                if c not in '01':\n",
    "                    left = dfs(s[:i])\n",
    "                    right = dfs(s[i+1:])\n",
    "                    for li, lv in enumerate(left):\n",
    "                        for ri, rv in enumerate(right):\n",
    "                            if c == '|':\n",
    "                                r = li | ri\n",
    "                            if c == '&':\n",
    "                                r = li & ri\n",
    "                            if c == '^':\n",
    "                                r = li ^ ri\n",
    "                            count[r] += lv * rv\n",
    "            return count\n",
    "        return dfs(s)[result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "        @cache\n",
    "        def dfs(expression, result):\n",
    "            # 边界情况\n",
    "            if len(expression) == 1:\n",
    "                val = int(expression)\n",
    "                return int(bool(val) == result)\n",
    "            \n",
    "            # 递归计算左右子式的结果\n",
    "            total = 0\n",
    "            for i in range(len(expression)):\n",
    "                if expression[i] in ops:\n",
    "                    for lr, rr in ops[expression[i]][result]:\n",
    "                        total += dfs(expression[:i], lr) * dfs(expression[i+1:], rr)\n",
    "            return total\n",
    "        return dfs(s, result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        memory = {}\n",
    "\n",
    "        def dfs(express, t):\n",
    "            if len(express) == 0:\n",
    "                ans = 1\n",
    "            elif len(express) == 1:\n",
    "                if int(express) == t:\n",
    "                    ans = 1\n",
    "                else:\n",
    "                    ans = 0\n",
    "            else:\n",
    "                if (express, t) in memory:\n",
    "                    ans =  memory[(express, t)]\n",
    "                else:\n",
    "                    ans = 0\n",
    "                    validPosSet = []\n",
    "\n",
    "                    # 找到算符的位置\n",
    "                    for pos in range(len(express)):\n",
    "                        ch = express[pos]\n",
    "                        if ch not in \"&|^\":\n",
    "                            continue\n",
    "                        else:\n",
    "                            validPosSet.append((pos, ch))\n",
    "            \n",
    "                    for pos, ch in validPosSet:\n",
    "                        left_exp, right_exp = express[:pos], express[pos+1:]\n",
    "\n",
    "                        left_0, left_1 = dfs(left_exp, 0), dfs(left_exp, 1)\n",
    "                        right_0, right_1 = dfs(right_exp, 0), dfs(right_exp, 1)\n",
    "                        \n",
    "                        if ch == \"&\":\n",
    "                            if t == 1:\n",
    "                                ans += left_1 * right_1\n",
    "                            else:\n",
    "                                ans += left_0 * right_1 + left_1 * right_0 + left_0 * right_0\n",
    "\n",
    "                        elif ch == \"|\":\n",
    "                            if t == 1:\n",
    "                                ans += left_0 * right_1 + left_1 * right_0 + left_1 * right_1\n",
    "                            else:\n",
    "                                ans += left_0 * right_0\n",
    "                        elif ch == \"^\":\n",
    "                            if t == 1:\n",
    "                                ans += left_0 * right_1 + left_1 * right_0\n",
    "                            else:\n",
    "                                ans += left_0 * right_0 + left_1 * right_1\n",
    "\n",
    "                    memory[(express, t)] = ans\n",
    "            #print(f\"{express} to {t}: {ans} possible\")\n",
    "            return ans\n",
    "        return dfs(s, result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        memory = {}\n",
    "\n",
    "        def dfs(express, t):\n",
    "            if len(express) == 0:\n",
    "                ans = 1\n",
    "            elif len(express) == 1:\n",
    "                if int(express) == t:\n",
    "                    ans = 1\n",
    "                else:\n",
    "                    ans = 0\n",
    "            else:\n",
    "                if (express, t) in memory:\n",
    "                    ans =  memory[(express, t)]\n",
    "                else:\n",
    "                    ans = 0\n",
    "                    validPosSet = []\n",
    "\n",
    "                    # 找到算符的位置\n",
    "                    for pos in range(len(express)):\n",
    "                        ch = express[pos]\n",
    "                        if ch not in \"&|^\":\n",
    "                            continue\n",
    "                        else:\n",
    "                            validPosSet.append((pos, ch))\n",
    "            \n",
    "                    for pos, ch in validPosSet:\n",
    "                        left_exp, right_exp = express[:pos], express[pos+1:]\n",
    "\n",
    "                        left_0, left_1 = dfs(left_exp, 0), dfs(left_exp, 1)\n",
    "                        right_0, right_1 = dfs(right_exp, 0), dfs(right_exp, 1)\n",
    "                        \n",
    "                        if ch == \"&\":\n",
    "                            if t == 1:\n",
    "                                ans += left_1 * right_1\n",
    "                            else:\n",
    "                                ans += left_0 * right_1 + left_1 * right_0 + left_0 * right_0\n",
    "\n",
    "                        elif ch == \"|\":\n",
    "                            if t == 1:\n",
    "                                ans += left_0 * right_1 + left_1 * right_0 + left_1 * right_1\n",
    "                            else:\n",
    "                                ans += left_0 * right_0\n",
    "                        elif ch == \"^\":\n",
    "                            if t == 1:\n",
    "                                ans += left_0 * right_1 + left_1 * right_0\n",
    "                            else:\n",
    "                                ans += left_0 * right_0 + left_1 * right_1\n",
    "\n",
    "                    memory[(express, t)] = ans\n",
    "            #print(f\"{express} to {t}: {ans} possible\")\n",
    "            return ans\n",
    "        return dfs(s, result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countEval(self, s: str, result: int) -> int:\n",
    "        ops = {\n",
    "            '&': {\n",
    "                True: [(True, True)],\n",
    "                False: [(True, False), (False, True), (False, False)]\n",
    "            },\n",
    "            '|': {\n",
    "                True: [(True, False), (False, True), (True, True)],\n",
    "                False: [(False, False)]\n",
    "            },\n",
    "            '^': {\n",
    "                True: [(True, False), (False, True)],\n",
    "                False: [(True, True), (False, False)]\n",
    "            }\n",
    "        }\n",
    "\n",
    "        @cache\n",
    "        def compute(s, target: bool):\n",
    "            if len(s) == 1:\n",
    "                return int(int(s) == target)\n",
    "\n",
    "            else:\n",
    "                count = 0\n",
    "\n",
    "                for i, x in enumerate(s):\n",
    "                    if x in ops:\n",
    "                        left = s[:i]\n",
    "                        right = s[i + 1:]\n",
    "                        pairs = ops[x][target]\n",
    "\n",
    "                        for left_target, right_target in pairs:\n",
    "                            count += compute(left, left_target) * compute(right, right_target)\n",
    "\n",
    "                return count\n",
    "\n",
    "        return compute(s, result)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
